package com.dubious.interview.euler;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;

public class Problem23 {

    private static int MAX_UNSUMMABLE_VALUE = 28123;
    
    /**
     * A perfect number is a number for which the sum of its proper divisors is exactly equal to
     * the number. For example, the sum of the proper divisors of 28 would be 
     * 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.
     * 
     * A number n is called deficient if the sum of its proper divisors is less than n and it is 
     * called abundant if this sum exceeds n.
     * 
     * As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can 
     * be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be 
     * shown that all integers greater than 28123 can be written as the sum of two abundant numbers.
     * However, this upper limit cannot be reduced any further by analysis even though it is known 
     * that the greatest number that cannot be expressed as the sum of two abundant numbers is less 
     * than this limit.
     * 
     * Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.
     */
    public static long run()
    {
        // strategy:
        // - find all abundant numbers up to the "known limit" of un-abundant-summable numbers
        // - sum all pair combinations of these abundant numbers and track in an array the sums
        //   that are found under the known limit.
        // - use the array to find the un-abundant-summable numbers and to sum those
        
        // find all abundant numbers up to the limit
        List<Integer> abundantNumbers = new ArrayList<Integer>();
        for(int i = 1; i <= MAX_UNSUMMABLE_VALUE; i++)
        {
            if(isAbundant(Long.valueOf(i)))
            {
                abundantNumbers.add(i);
            }
        }
        
        // sum all combinations of abundant numbers and mark the values which result
        boolean[] isSummable = new boolean[MAX_UNSUMMABLE_VALUE + 1];
        for(int i = 0; i < abundantNumbers.size() - 1; i++)
        {
            for(int j = i; j < abundantNumbers.size(); j++)
            {
                int sum = abundantNumbers.get(i) + abundantNumbers.get(j);
                if(sum <= MAX_UNSUMMABLE_VALUE)
                {
                    isSummable[sum] = true;
                }
            }
        }
        
        // use the array to find the unsummable numbers and sum those
        long result = 0;
        for(int i = 0; i < MAX_UNSUMMABLE_VALUE; i++)
        {
            if(!isSummable[i])
            {
                result += i;
            }
        }
        
        return result;
    }
    
    private static boolean isAbundant(Long i)
    {
        // retrieve the set of perfect divisors
        Set<Long> divisors = Utilities.getDivisors(i);
        divisors.remove(i);
        
        long divisorsSum = 0;
        for(Long divisor : divisors)
        {
            divisorsSum += divisor;
        }
        
        return divisorsSum > i;
    }
}
